import java.util.*;

public class test {
    // leetcode 376.摆动序列
    // 1. 动态规划解法
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        // 1. 创建dp表
        // 存在两种状态(递增态)(递减态)
        // [0]代表以当前值为最后一个数,下次递增
        // [1]代表以当前值为最后一个数,下次递减
        int[][] dp = new int[n][2];
        // 2. 初始化
        dp[0][0] = 1;
        dp[0][1] = 1;
        // 3. 填表
        for(int i = 1;i < n;i++){
            if(nums[i] > nums[i - 1]){
                dp[i][0] = dp[i - 1][1] + 1;
                dp[i][1] = dp[i - 1][1];
            }else if(nums[i] < nums[i - 1]){
                dp[i][1] = dp[i - 1][0] + 1;
                dp[i][0] = dp[i - 1][0];
            }else {
                dp[i][1] = dp[i - 1][1];
                dp[i][0] = dp[i - 1][0];
            }
        }
        // 4. 返回值
        return Math.max(dp[n - 1][0],dp[n - 1][1]);
    }
    // leetcode 179.最大数
    public String largestNumber(int[] nums) {
        int len = nums.length;
        String[] arr = new String[len];
        for(int i = 0;i < len;i++){
            arr[i] = String.valueOf(nums[i]);
        }
        // 贪心思想:
        // 其实就是一种特定规则的排序
        // 每次都选择当前的最优选项(拼接后最大的两个字符串)
        Comparator<String> comparator = new Comparator<String>() {
            @Override
            public int compare(String a,String b) {
                String s1 = a + b;
                String s2 = b + a;
                return s2.compareTo(s1);
            }
        };
        Arrays.sort(arr,comparator);
        if(arr[0].equals("0")) return "0";
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 0;i < len;i++){
            stringBuilder.append(arr[i]);
        }
        return stringBuilder.toString();
    }
    // leetcode 2208.将数组和减半的最少操作次数
    public int halveArray(int[] nums) {
        // [5,19,8,1]
        // 操作数
        int num = 0;
        double sum = 0;
        double key = 0;
        double sub = 0;
        PriorityQueue<Double> queue = new PriorityQueue<>(Collections.reverseOrder());
        for(int i = 0;i < nums.length;i++){
            sum += nums[i];
            queue.add((double)nums[i]);
        }
        key = sum / 2.0;
        while(sub < key){
            double n = queue.poll();
            n /= 2.0;
            sub += n;
            queue.add(n);
            num++;
        }
        return num;
    }
}
